1. Field of the Invention
The present invention is directed to a system which builds a database of image graphs, and which retrieves images that are similar to a xe2x80x9cqueryxe2x80x9d image using this database. Specifically, the invention generates graphs of images based on homogeneous regions thereof, and stores these graphs in the database, together with pointers to the images. The invention then generates a similar graph for the query image, and compares the query image graph to the graphs in the database. Those graphs in the database that are similar to the query image graph are identified, and their corresponding images retrieved.
2. Description of the Related Art
In recent years, it has become commonplace for personal computers and other digital hardware to process and display digital images. This is due, in no small part, to the increase in popularity of digital video on the Internet. As a result of this increased use of digital imagery, it has become necessary to retrieve images from increasingly larger image databases. This typically does not present a problem if there is some way to readily identify the images, such as via a file name or the like.
On the other hand, it is more difficult to retrieve images from a large database if the only way to retrieve the images is based on their content, as is oftentimes the case, e.g., for digital video and for scanned images. For example, a user may wish to locate a video clip based on a single frame of video, or to locate particular frame of video within a video clip. Similarly, a user may wish to determine which of a plurality of pre-stored images best matches a scanned image. In these cases, image retrieval can be difficult.
Current methods of retrieving images, such as frames of video, from a database involve labeling the individual frames, and then searching through the frames manually for particular frames based on these labels. As might be expected, this process is both time consuming and inefficient. Automated content-based image retrieval systems exist. However, these systems are often slow due to the amount of processing required, and often produce erroneous results, particularly for images having different orientations, rotations, scaling, translations, and aspect ratio variations.
Accordingly, there exists a need for an automated content-based image retrieval system that addresses these and other drawbacks of conventional systems. In particular, there exists a need for a system which provides for content-based image retrieval that is both accurate and fast.
The present invention addresses the foregoing needs by providing a method of building a database from which images, such as frames of video, can be retrieved based on their content. In more detail, the invention inputs images, divides the images into one or more regions based on one or more attributes of the image, such as color, texture, etc., and generates a graph of the regions. This graph is then stored in the database, together with a pointer to the image. This database can then be used to retrieve one or more images (e.g., frames of video) that are similar to an input, or xe2x80x9cqueryxe2x80x9d image.
To this end, the invention performs substantially the same processing on the query image as that performed to generate the graphs in the database. That is, the invention divides the query image into regions based on one or more attributes of the image, and generates a graph based on the regions. Thereafter, the graph for the query image is compared to graphs in the database. Images are then retrieved whose graphs have at least a predetermined level of similarity to the xe2x80x9cquery imagexe2x80x9d graph. Alternatively, the system retrieves a fixed number of the most similar images, such as the ten images whose graphs are most similar to the query image graph.
By virtue of the foregoing, the present invention provides a way to retrieve images based on content that operates automatically, rather than manually. In other words, the invention eliminates the necessity of physically labeling images, such as frames of video, and then manually xe2x80x9cflipping throughxe2x80x9d those images to locate an image that is similar to a query image. Moreover, because the invention compares image graphs, and particularly features thereof, the invention is able to determine whether two images are similar regardless of image orientation, rotation, scaling, translation, and aspect ratio variations.
Thus, according to one aspect, the present invention is a system (i.e., a method, an apparatus, and computer-executable process steps) for building a database of image-related data. The system inputs a plurality of images, such as key frames of a video sequence. For each input image, the system divides (or xe2x80x9csegmentsxe2x80x9d) the image into N1 (N1xe2x89xa71) regions which are substantially homogenous with respect to one or more attributes of the image, and generates a graph based on M1 (M1xe2x89xa71) of the N1 regions, where M1 may, or may not, equal N1. The system then stores data for the graph in the database.
According to another aspect, the invention is a system which uses graphs corresponding to a plurality of images to determine whether a query image is similar to one or more of the plurality of images. In operation, the system inputs the query image, divides the query image into N2 (N2xe2x89xa71) regions which are substantially homogenous with respect to one or more attributes of the query image, and generates a graph based on M2 (M2xe2x89xa71) of the N2 regions, where one or more individual values of N1, N2, M1 and M2 may or may not be equal. The system then compares the generated graph to other graphs in a database that correspond to the plurality of images, and retrieves one or more images having graphs that substantially correspond to the graph of the query image.
This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiment thereof in connection with the attached drawings.